package leetcode.editor.cn.dsa13_mergesort;

public class BinarySearch {

    // 二分查找算法，在a[start] ~ a[end]中查找key
    public int binarySearch(int key, int[] a, int start, int end) {
        if (start > end) return -1; // 未找到key，返回-1
        int m = (start + end) / 2;
        if (a[m] == key) return m; // 找到key，返回key的索引
        if (a[m] > key)
            return binarySearch(key, a, start, m - 1); // 在m左侧继续查找
        return binarySearch(key, a, m + 1, end); // 在m右侧继续查找
    }
}
